1) Field of the Invention
The present invention relates to a technology for generating a test pattern to detect an error in a logic circuit.
2) Description of the Related Art
Test patterns are used to detect errors in logic circuits. Such test patterns can be generated automatically by using a tool called Automatic Test Pattern Generation (hereinafter, “ATPG”), if the structure of the logic circuit is given.
However, it takes a very long time for the ATPG to generate the test pattern if the circuit is large scale. A method to solve this problem is disclosed in Japanese Patent-Application Laid-Open Publication No. H5-5774. With this method, a test pattern is easily generated by cutting out only the relevant section of the circuit, and then simplifying the cut out section.
There are also other approaches, such as a method of generating a test pattern by static learning/dynamic learning, or learning based on observability/controllability. The static learning/dynamic learning method performs implication processing, so that an arbitrary net-a (input value) determines a logic value for a net-b (output value) in the circuit, and a computer learns the relationship between net-a and net-b. Hence, the number of combinations of logic values can be reduced.
In a complex circuit, a contradiction is often found during the implication processing. The observability/controllability-based learning method performs implication processing from a section where such a contradiction is easily observable or from a complex section, so as to determine at an early stage whether the test pattern can be generated.
However, the known methods are inefficient or inapplicable when generating a test pattern for an error correcting circuit (hereinafter, “ECC”), which is typically used in a Random Access Memory (hereinafter, “RAM”), or a latch circuit, etc.
Specifically, the ECC includes a plurality of Exclusive OR (hereinafter, “EOR”) circuits that share a common input value. Therefore, it cannot be determined whether a request value of the EOR circuits generated in the implication processing, contradicts with output values corresponding to a certain input value of the EOR circuits.
FIG. 14 is an example of the ECC. The ECC includes a syndrome computing section 1 and a corrected-data computing section 2. The syndrome computing section 1 includes EOR circuits 3a to 3c and calculates a syndrome s from a reception word y. The corrected-data computing section 2 uses all of the bit components of the-syndrome s, to calculate a corrected data word m.
The syndrome s is obtained from the following equation:S=H·yt(mod 2)where y is a reception word vector that is input to the syndrome computing section 1, H is an inspection matrix of the syndrome computing section 1, yt is a transposed vector of vector y, and mod 2 is a remainder operator having a modulus of 2.
For example, a test pattern to detect an error in a signal line in the corrected-data computing section 2 is generated as follows. When the error propagates, a request value sr is generated. Then, the logic value corresponding to the reception word y, is searched for the request value Sr.
However, the reception word y is partially shared by the EOR circuits 3a to 3c. Therefore, the EOR circuits 3a to 3c cannot independently determine an output value. Moreover, the EOR circuits 3a to 3c cannot determine an output value unless all input values are determined. Thus, a contradiction cannot be immediately detected between an output value (syndrome) sy calculated from the input value of the reception word y, and the request value sr.
Specifically, in the test-pattern generation processing, a logic value is determined for an-arbitrary net in an EOR circuit, into which a reception word y of n bits is input. Here, it is required to determine an input value of n−i bits (i ranges from 1 to n−1, according to the configuration of the inspection matrix H). Otherwise, a contradiction between the request value sr and the output value sy cannot be detected surely.
When a contradiction is detected by the implication processing for the reception word y, the implication processing is continued by performing backtrack. However, if the request value sr contradicts with the output value sy in the first place, the search needs to be executed 2n−1 times until the contradiction is detected. Consequently, the processing takes a very long time if the number of bits n is large.
In the static/dynamic learning method, the output value from the EOR circuit cannot be determined unless all of the input values are determined. Therefore, even if a certain bit value of the reception word y is set as a bit value of net-a, net-b does not exist. Accordingly, there are no relationships for the computer to learn, until all input values are determined.
As to the observability/controllability-based learning method, the order of the implication processing can be changed. However, it is meaningless to change the order because the output value cannot be determined unless all input values are determined.
It is therefore imperative to achieve an efficient method of generating a test pattern to detect an error in a logic circuit such as the ECC that includes an EOR circuit.